# 计算一个数字的平方根。这个其实没有多少编程思想，主要是数学公式
import math
# 袖珍计算器法：就是转换成指数形式的东西可以进行计算
def mySqrt(x):
    if x == 0:
        return 0
    ans = math.exp(0.5 * math.log(x))
    return ans + 1 if (ans + 1) ** 2 <= x else ans

# 牛顿法:选择一个点，不断在曲线上求该点的切线。最终迭代的差值变换非常小时就可以得到最终的结果了
def mySqrt(x):
    if x == 0: return 0
    C = x
    x0 = x
    while True:
        xi = 0.5 * (x0 + C/x0)
        if abs(x0-xi) < 1e-7:
            break
        x0 = xi
    return int(x0)

# 二分查找：注意模板
# 二分查找往往需要关注的是取左中位数还是右中位数(我一般习惯左中位数)。后一个就是left和right如何变化更新的问题。这个考虑例子来确定是否加一减一。
# 这个二分查找的边界问题一定要弄好。不然会遇到大问题
def mySqrt(x):
    left = 0
    right = x
    ans = -1
    while left <= right:
        mid = (left + right) // 2
        s = mid ** 2
        if s > x:
            right = mid - 1
        else:
            ans = mid
            left = mid + 1
    return ans